package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname Combinations
 * @Description Leetcode 77 组合 中等难度 回溯算法
 * @Date 2021/9/28 18:52
 * @Version 1.0
 */
public class Combinations {


    List<List<Integer>> result = new ArrayList<>();

    /**
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {


        List<Integer> combine = new LinkedList<>();
        backtrack(combine, n, k, 0, 1);

        return result;

    }


    /**
     * @param combine
     * @param n
     * @param k
     * @param cnt
     * @param startIndex
     */
    private void backtrack(List<Integer> combine, int n, int k, int cnt, int startIndex) {

        if (k == cnt) {
            result.add(new LinkedList<>(combine));
            return;
        }

        for (int i = startIndex; i <= n; i++) {


//            visited[i] = true;
            combine.add(i);
            backtrack(combine, n, k, cnt + 1, i + 1);
//            visited[i] = false;
            combine.remove(combine.size() - 1);

        }
    }


    public static void main(String[] args) {
        Combinations combinations = new Combinations();

        List<List<Integer>> lists = combinations.combine(4, 2);


        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}
